package com.leetcode.partition5;

import com.leetcode.common.TreeNode;

import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/18 10:34
 */
public class LC404左叶子之和 {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root.left == null && root.right == null) return 0;
        return iteration(root);
    }

    public static void main(String[] args) {
        TreeNode r1 = new TreeNode(3, null, new TreeNode(20, null, new TreeNode(7)));
        System.out.println(new LC404左叶子之和().sumOfLeftLeaves(r1));
    }

    private int iteration(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        int sum = 0;
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            if (cur.left != null && cur.left.left == null && cur.left.right == null) sum += cur.left.val;
            if (cur.right != null) s.push(cur.right);
            if (cur.left != null) s.push(cur.left);
        }
        return sum;
    }

    private int recursion(TreeNode root) {
        if (root == null) return 0;
        int leftLeftLeaves = recursion(root.left);      //求左子树的左叶子之和
        int rightLeftLeaves = recursion(root.right);    //求右子树的左叶子之和
        int mid = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) mid += root.left.val;
        return leftLeftLeaves + rightLeftLeaves + mid;
    }
}
